#define _CRT_SECURE_NO_WARNINGS 1

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;

    Node() {}

    Node(int _val) {
        val = _val;
        next = NULL;
    }

    Node(int _val, Node* _next) {
        val = _val;
        next = _next;
    }
};
*/

class Solution {
public:
    Node* insert(Node* head, int insertVal)
    {
        if (head == nullptr)
        {
            Node* newNode = new Node(insertVal);
            newNode->next = newNode;
            return newNode;
        }

        Node* maxValNode = head;
        Node* cur = head->next;
        while (cur != head)
        {
            if (cur->val >= maxValNode->val)
            {
                maxValNode = cur;
            }
            cur = cur->next;
        }

        Node* minValNode = maxValNode->next;

        if (insertVal <= minValNode->val || insertVal >= maxValNode->val)
        {
            Node* newNode = new Node(insertVal);
            newNode->next = minValNode;
            maxValNode->next = newNode;
            return head;
        }

        cur = minValNode;
        while (true)
        {
            if (cur->val <= insertVal && cur->next->val >= insertVal)
            {
                Node* next = cur->next;
                Node* newNode = new Node(insertVal);
                cur->next = newNode;
                newNode->next = next;
                break;
            }
            cur = cur->next;
        }

        return head;
    }
};